home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Libraries / objects in c ƒ / OIC Sources / List.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-05  |  6.7 KB  |  362 lines  |  [TEXT/KAHL]
  1. /*    
  2.  *        List abstract class
  3.  *
  4.  *            Copyright © John Wainwright 1988
  5.  *
  6.  *        head l            - returns first item in list l
  7.  *        tail l            - returns list l minus 1st item
  8.  *        append l item    - appends item to list l
  9.  *        delete l item    - surgically deletes item ( by == ) from list
  10.  *        push l item     - pushes item on front of l
  11.  *        join l1 l2        - joins list2 to end of list1
  12.  *        isEmpty l        - returns non-zero if list is empty, ,zero if not
  13.  *        equal l1 l2        - test isomorphic equality between l1 & l2
  14.  *        new l itemlist    - builds new list
  15.  *        add l itemList    - adds items to list
  16.  *        nth i l            - nth item in list
  17.  *        second l        - second item in list
  18.  *        third l            - third item in list
  19.  *      sequence l        - returns an initialised sequence object containing l
  20.  *        forAll l f args    - invokes function on each element of l
  21.  *        copy l            - returns a new list which is a copy of l
  22.  *        deepCopy l        - returns a deep copy of l
  23.  *        dispose l        - disposes the list structure l (but not the items)
  24.  *        deepDispose l    - dispose l and sends 'deepDispose' to all it contains
  25.  *        print l            - outputs nicely formatted list l to stdout
  26.  *        repList l        - returns a representation (ascii) list for l
  27.  */
  28.  
  29. #include "oic.h"
  30. #include "generics.h"
  31.  
  32. class       List;            /* the list class                         */
  33.  
  34. typedef struct                /* list instance structure                 */
  35. {
  36.     list      l_next;
  37.     object    l_item;
  38. } list_i;
  39.  
  40. /* -------------------- List Instance methods ---------------------------- */
  41.  
  42. method list  
  43. _new(self, l, items)
  44.     object            self;
  45.     register list_i    *l;
  46.     register object    *items;
  47. {
  48.     while (*items != END)
  49.         append(self, *items++);
  50.         
  51.     return Super(self);
  52. }
  53.  
  54. method object
  55. _head(self, list)   
  56.     object            self;
  57.     register list_i *list;
  58. {
  59.     return list->l_item;
  60. }
  61.  
  62. method list  
  63. _tail(self, list)
  64.     object             self;
  65.     register list_i    *list;
  66. {
  67.     return (list->l_item == END) ? self : list->l_next;
  68. }
  69.  
  70. method list  
  71. _append(self, l, item)
  72.     object            self;
  73.     register list_i    *l;
  74.     object            *item;
  75. {
  76.     register list_i *li;
  77.  
  78.     for (li = l; li->l_item != END; li = localIVs(li->l_next, list_i));
  79.     li->l_next = New(List, END);
  80.     li->l_item = *item;
  81.  
  82.     return self;
  83. }
  84.  
  85. method list  
  86. _join(self, l, list2)
  87.     object            self;
  88.     register list_i    *l;
  89.     object            *list2;
  90. {
  91.     register list_i *l1, *l2;
  92.  
  93.     l2 = localIVs(*list2, list_i);
  94.     for (l1 = l; l1->l_item != END; l1 = localIVs(l1->l_next, list_i));
  95.     l1->l_next = l2->l_next;
  96.     l1->l_item = l2->l_item;
  97.  
  98.     return self;
  99. }
  100.  
  101. method list  
  102. _push(self, l, item)
  103.     object            self;
  104.     register list_i    *l;
  105.     object            *item;
  106. {
  107.     register list      newl;
  108.     register list_i *newinst;
  109.  
  110.     newl = New(List, END);
  111.     newinst = localIVs(newl, list_i);
  112.     newinst->l_next = l->l_next;
  113.     newinst->l_item = l->l_item;
  114.     l->l_next = newl;
  115.     l->l_item = *item;
  116.  
  117.     return self;
  118. }
  119.  
  120. method int
  121. _isEmpty(self, l)
  122.     object            self;
  123.     register list_i *l;
  124. {
  125.     return (l->l_item == END);
  126. }
  127.  
  128. method int
  129. _equal(self, l, otherlist)
  130.     object    self;
  131.     list_i    *l;
  132.     list      *otherlist;
  133. {
  134.     register object    head1, head2;
  135.  
  136.     head1 = head(self);
  137.     head2 = head(*otherlist);
  138.     
  139.     if (head1 == END && head2 == END)
  140.         return 1;
  141.     if (head1 == END || head2 == END)
  142.         return 0;
  143.     if ((int)equal(head1, head2))
  144.         return ((int)equal(tail(self), tail(*otherlist)));
  145.     else
  146.         return 0;
  147. }
  148.  
  149. method list  
  150. _add(self, l, items)
  151.     object            self;
  152.     register list_i    *l;
  153.     register object    *items;
  154. {
  155.     while (*items != END)
  156.         append(self, *items++);
  157.         
  158.     return self;
  159. }
  160.  
  161. method object
  162. _sequence(self)
  163.     object    self;
  164. {
  165.     return start(New(Linkseq), self);
  166. }
  167.  
  168. method object
  169. _assoc(self, l, key)
  170.     object            self;
  171.     register list_i    *l;
  172.     object            *key;
  173. {
  174.     register list_i *lp;
  175.  
  176.     for (lp = l; lp->l_item != END; lp = localIVs(lp->l_next, list_i))
  177.         if (ClassOf(lp->l_item) == List && equal(head(lp->l_item), *key))
  178.             return head(tail(lp->l_item));
  179.     
  180.     return END;
  181. }
  182.  
  183. method object
  184. _delete(self, l, ip)
  185.     object            self;
  186.     register list_i    *l;
  187.     register object    *ip;
  188. {
  189.     register object this;
  190.     register list_i    *pl;
  191.  
  192.     for (this = self;
  193.         l->l_item != *ip && l->l_item != END;
  194.         pl = l, this = l->l_next, l = localIVs(this, list_i))
  195.         ;
  196.     
  197.     if (l->l_item == *ip)
  198.     {
  199.         if (this == self)            /* removing head        */
  200.             self = l->l_next;
  201.         else
  202.             pl->l_next = l->l_next;
  203.         free(this);
  204.     }
  205.          
  206.     return self;
  207. }
  208.     
  209. method object
  210. _nth(self, l, n)
  211.     object            self;
  212.     register list_i    *l;
  213.     int                *n;
  214. {
  215.     register list_i *lp;
  216.     register int    i;
  217.  
  218.     for (lp = l, i = 0; i < *n && lp->l_item != END; i++, lp = localIVs(lp->l_next, list_i))
  219.         ;
  220.     
  221.     return lp->l_item;
  222. }
  223.     
  224. method object
  225. _second(self)
  226.     object            self;
  227. {
  228.     return head(tail(self));
  229. }
  230.     
  231. method object
  232. _third(self)
  233.     object            self;
  234. {
  235.     return head(tail(tail(self)));
  236. }
  237.     
  238. method object
  239. _repList(self, l, ap)
  240.     object    self;
  241.     list_i    *l;
  242.     void    *ap;
  243. {
  244.     register list_i *lp;
  245.     register object    replist;
  246.  
  247.     replist = New(Replist, "(", ")", " ");
  248.     if (l->l_item == END)
  249.         append(replist, New(String, "EMPTY"));
  250.     else
  251.     {
  252.         for (lp = l; lp->l_item != END; lp = localIVs(lp->l_next, list_i))
  253.             append(replist, repList(lp->l_item));
  254.     }
  255.  
  256.     return replist;
  257. }
  258.  
  259. method
  260. _deepDispose(self, li, ap)
  261.     object            self;
  262.     register list_i    *li;
  263.     void            *ap;
  264. {
  265.     register object    lo, nextl;
  266.  
  267.     if (li->l_item != END)
  268.     {
  269.         deepDispose(li->l_item);
  270.         for (lo = li->l_next; (li = (localIVs(lo, list_i)))->l_item != END; lo = nextl)
  271.         {
  272.             nextl = li->l_next;
  273.             deepDispose(li->l_item);
  274.             free(lo);
  275.         }
  276.     }
  277.     
  278.     free(self);
  279. }
  280.     
  281. method void
  282. _forAll(self, l, ap)
  283.     object            self;
  284.     register list_i    *l;
  285.     register struct 
  286.     {
  287.         void    (*f)();
  288.         double    a1, a2, a3, a4, a5;
  289.     } *ap;
  290. {
  291.     register list_i *lp;
  292.  
  293.     for (lp = l; lp->l_item != END; lp = localIVs(lp->l_next, list_i))
  294.         (*ap->f)(lp->l_item, ap->a1, ap->a2, ap->a3, ap->a4, ap->a5);
  295. }
  296.  
  297. method void
  298. _forAllGen(self, l, ap)
  299.     object        self;
  300.     register list_i    *l;
  301.     struct 
  302.     {
  303.         generic    gen;
  304.         char    *args;
  305.     } *ap;
  306. {
  307.     register list_i *lp;
  308.  
  309.     for (lp = l; lp->l_item != END; lp = localIVs(lp->l_next, list_i))
  310.         ApplyGeneric(ap->gen, lp->l_item, ap->args);
  311. }
  312.  
  313. method
  314. _dispose(self, li)
  315.     object            self;
  316.     register list_i    *li;
  317. {
  318.     register object    lo, nextl;
  319.  
  320.     if (li->l_item != END)
  321.     {
  322.         for (lo = li->l_next; (li = (localIVs(lo, list_i)))->l_item != END; lo = nextl)
  323.         {
  324.             nextl = li->l_next;
  325.             free(lo);
  326.         }
  327.     }
  328.     
  329.     free(self);
  330. }
  331.     
  332. /* ------------------- Init the List class ------------------------------- */
  333.  
  334. InitList()
  335. {
  336.     List = NewClass(sizeof(list_i), 0, "List", END);
  337.     AddMethods(List,
  338.         addGeneric,            _add,
  339.         appendGeneric,         _append,
  340.         assocGeneric,        _assoc,
  341.         forAllGeneric,        _forAll,
  342.         forAllGenGeneric,    _forAllGen,
  343.         joinGeneric,         _join,
  344.         pushGeneric,        _push,
  345.         headGeneric,        _head,
  346.         tailGeneric,        _tail,
  347.         mapGeneric,            _forAll,
  348.         nthGeneric,            _nth,
  349.         secondGeneric,        _second,
  350.         thirdGeneric,        _third,
  351.         isEmptyGeneric,        _isEmpty,
  352.         equalGeneric,        _equal,
  353.         sequenceGeneric,    _sequence,
  354.         disposeGeneric,        _dispose,
  355.         deepDisposeGeneric, _deepDispose,
  356.         newGeneric,            _new,
  357.         repListGeneric,        _repList,
  358.         deleteGeneric,        _delete,
  359.         END);
  360. }
  361.  
  362.